package com.summer.study.leetcode.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * @auther: 杨杰
 * @date: 2019/7/29 18:11
 * @description: 求众数
 * https://leetcode-cn.com/problems/majority-element
 */
public class majority_element_169 {

    public static int majorityElement2(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for (Integer item : nums) {
            if (!map.containsKey(item)) {
                map.put(item, 1);
            } else {
                int count = map.get(item);
                map.put(item, count + 1);
            }
            if (map.get(item) > nums.length / 2) {
                return item;
            }
        }
        return -1;

    }

    public static int majorityElement(int[] nums) {
        int temp = nums.length / 2;
        System.out.println(temp);
        for (int item : nums) {
            int count = 0;
            for (Integer item2 : nums) {
                if (item2 == item) {
                    count++;
                }
            }
            if (count > temp) {
                return item;
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 1, 1, 1, 2, 2, 2, 5};

        System.out.println(majorityElement2(nums));
    }

}
